package com.datastructure.test.findsumofpath;

public class FindSumOfPath {

    public static void main(String[] args) {
        FindSumOfPath findSumOfPath = new FindSumOfPath();
        TreeNode treeNode = new TreeNode(1);
        treeNode.right=new TreeNode(2);
        treeNode.right.right=new TreeNode(3);
        treeNode.right.right.right=new TreeNode(4);
        int findPath = findSumOfPath.FindPath(treeNode, 3);
        System.out.println(findPath);
    }

    public int sumOfPath = 0;
    public int FindPath (TreeNode root, int sum) {
        // write code here
        if(root==null){
            return 0;
        }
        computePath(root,sum);
        return sumOfPath;
    }

    public void computePath(TreeNode root, int sum){
        computeFindPath(root,0,sum);
        if(root.left!=null){
            computePath(root.left,sum);
        }
        if(root.right!=null){
            computePath(root.right,sum);
        }
    }

    private void computeFindPath(TreeNode root, int sum,int target) {
        if(root==null){
            return;
        }
        sum+= root.val;
        if(sum==target){
            sumOfPath++;
        }
        computeFindPath(root.left,sum,target);
        computeFindPath(root.right,sum,target);
    }

}

class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
   public TreeNode(int val) {
     this.val = val;
   }
 }
